1. Field of the Invention
This invention relates generally to artificial intelligence (AI) "expert systems" or "knowledge-based systems." The invention is more specifically related to an expert system for configuring complex system components which uses declaratively constructed graphs for the knowledge representation and multiple interacting packing engines.
2. Background Information
Knowledge-based expert systems incorporate one or more techniques of artificial intelligence to employ human knowledge to solve problems that ordinarily require human intelligence. These expert systems are often formed of computer hardware/software combinations which are structured to mimic the behavior of a human having expert knowledge in a particular field. The expert knowledge is typically contained in a data base called the "knowledge base." The knowledge base may consist of production rules, semantic networks, frames, conceptual dependency graphs, or other paradigms of knowledge representation. The expert system contains one or more inference engines. An inference engine is a logical module which interacts with the knowledge base to generate consequences, conclusions, or decisions from the existing knowledge. It may be a rule interpreter or it may arrive at conclusions by propagating state information in a probabilistic inference network.
For a general explanation of artificial intelligence, knowledge representation, and expert systems, the reader is directed to references such as "Introduction to Artificial Intelligence," by Eugene Charniak and Drew McDermott, Addision Wesley Publishing Company, 1985; "The Handbook of Artificial Intelligence" Vol. 1 (1981) and Vol. 2 (1982) edited by Avron Barr and Edward Feigenbaum, and Vol. 3 (1982), edited by Paul Cohen and Edward Feigenbaum, William Kaufmann, Inc.; "The Hitch-Hiker's Guide to Artificial Intelligence," by Richard Forsyth and Chris Naylor, Chapman and Hall Ltd./Methuen London Ltd., 1985; and "The Encyclopedia of Artificial Intelligence," edited by Stuart C. Shapiro, John Wiley & Sons, 1987.
Knowledge bases may be built with one of two kinds of aids. One kind conducts an "interview" with an expert, asking the expert repeatedly for information. It builds up a relational structure from the expert's responses. These tools are called expertise-transfer systems. The other kind of aid is a structured editor or language that allows a trained knowledge engineer to easily add information to the knowledge base (or delete or modify the information). For example, such a system may allow the user to view, add, or remove a list of production rules, with the system checking the rules' syntax. There are several commercial expert system "shells" available that provide these capabilities.
Relatively simple expert systems can be constructed effectively using this second kind of tool and a production-rule format. An early expert system was the R1 family of knowledge-based systems. R1, later called XCON, is a domain-specific, rule-based expert system which solves a problem which is intractable using conventional data processing methods. The generation of a correct configuration of a computer system requires applying thousands of heuristic rules to capture the full variety of engineering components and relationships between the supported components. Human experts can apply these rules to generate a possible configuration, but there is no guarantee that the configuration will be correct, that is, that it can be manufactured and work properly. Furthermore, the goal of an optimal configuration solution may be beyond the capabilities of any human. R1 parses a customer's purchase order to determine what, if any, substitutions and additions of components have to be made to the purchase order to make it consistent and complete. It arrives at a solution by using its knowledge of the computer system configuration domain and of the peculiarities of the various configuration constraints.
The R1 system, developed by Carnegie Mellon University and Digital Equipment Corporation (DEC), is based on a production system model and written in OPS-5, a programming language particularly suited for production systems. The basic features of a production system as a knowledge representation are a global database containing the basic knowledge and the results of the computation so far, and a set of production rules that operate on the database. A production rule consists of a procedure called the body of the rule and an associated pattern. Inference processing in such a system consists of a cycle in which a rule s found whose pattern matches a portion of the database, and then the rule's body is executed. Execution of the body of a rule will generally make changes to the database by adding, deleting, or modifying data structures in the database. OPS-5 provides a simple, but uniform representation method for describing problem-solving state data and for specifying rule conditions that match this state data. However, OPS-5 provides little structure for representing facts, relationships, and uncertainty. Thus it does not provide a convenient general architecture for problem-solving. Additionally, to program the action components of rules, OPS-5 requires a knowledge engineer to write program code in a specialized programming language.
The R1 system had several drawbacks. Originally, it was specific to the VAX 11/780 computer system produced by DEC. Therefore it was a specialized configurator. Its capabilities have gradually been expanded to other DEC computer systems, but at the expense of adding more rules. As the number of rules expanded into the thousands, the system became slow. Some rules in the knowledge base were redundant. Because the configuration knowledge was based on rules, component constraint information was embodied in rules that were necessarily "hard-coded" by computer programmers from expert knowledge rather than written by an expert in a declarative fashion. Hence, performing maintenance and adding enhancements to R1 became very difficult as the system grew larger. The original R1 was not interactive; a user could not easily set up different, alternative configurations.
An expert system for configuring communications networks is disclosed in U.S. Pat. No. 5,175,800, issued to Galis, et. al. This invention allows a user to define and maintain databases of configuration knowledge and requirements information. The system validates the user's requirements or changes to requirements for a communications network and produces an expert configuration data set of options for full and partial configuration efforts. The system is rule-based, the embedded rules specifying the legal connections between network devices. Hence it is susceptible to the same kinds of problems as the R1 system. The Galis, et. al. system is a special purpose configurator. It is designed primarily for communications networks including time division multiplexing (TDM) devices. Its man machine interface guides the user to enter data and commands to make configuration decisions for a communications network. The special purpose nature of this invention restricts its application to communications network configuration problems.
An expert system for designing a connected collection of components which may be described by variable characteristics is disclosed in U.S. Pat. No. 5,293,479, issued to Quintero, et. al. This invention includes a knowledge base and an inference engine. The knowledge base includes information relating to constant and variable characteristics of the connectable components and rules for combining these components. The inference engine interprets the rules in order to legally connect the components per user requests. The Quintero, et. al. system exhibits flaws similar to the R1 and Galis, et. al. systems, in that it is rule-based and directed to a specialized problem domain (in this case, modular furniture assembly).
Several existing special purpose configurators take different approaches to solving the configuration problem for computer systems. One system, used specifically for the 2200 Series computer systems produced by Unisys Corporation, employs large portions of iterative code and specialized data structures to represent the large variety of system components available and to solve component cabling (or "stringing") problems. Another system, for the "A" Series computer systems sold by Unisys, also uses specialized data structures written in a standard high level language to represent components, which are manipulated to solve component packing problems. Its packing logic modules execute in predefined sequences, with no dynamic ordering. Consequently, it sometimes produces anomalous cases of very poor results. A third system for configuring personal computer (PC) systems is based on the concept of a spreading activation network. This system works effectively for simple configurations, but as the complexity level grows, the spreading activation network becomes too convoluted to be processed properly. Each of the above approaches requires major program code modifications to change the way components can be connected, add or delete possible system components, or support other models of computer systems.
A product configurator tool based on an object-oriented design methodology is commercially available from the Trilogy Development Group. In the Trilogy configurator, called "SalesBuilder," each part or component to be configured is represented by a software object. Thus, knowledge in this system is based on objects and not rules. The Trilogy system uses an underlying Structured Query Language (SQL) database manager to develop a customized product configuration system, which is then used by a company as a sales and marketing tool. This system is implemented in the C++ programming language in order to take advantage of the available features of hierarchy or objects and class inheritance. The object-oriented design approach works well for relatively small configuration problems, such as for a PC, but is insufficient for the complex configurations inherent in large mainframe computer systems.
A flexible, generalized configurator is needed to manage the various levels of complexity for configuration problems. Many products which are composed of a large number of interconnected parts undergo continuous change in their product set and packaging. Keeping up with the constant state of flux of product lines is a difficult and time-consuming task for a large number of users. Special purpose expert systems, often using special databases, can address parts of this configuration problem, but they occasionally create results that are obviously sub-optimal, or are limited to subsets of the total problem. Such systems also impose a major maintenance burden. Therefore, a generalized configurator should be easily defined and modified. Previously installed configurations often have a long life, yet customers of a particular product have the need from time to time for replacement components that may or may not be currently manufactured. Thus, the configurator must support historical data to allow for old, legacy components. There is usually widely varying expertise among configurator users, so a configurator should be able to provide "manual" control for experienced users and an automatic mode for novice users. Finally, the sheer complexity of the configuration problem may demand automatic answers to problems too complicated for humans to adequately and efficiently solve.